public class Test02 {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || m == n) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
        }

        ListNode start = prev.next;
        ListNode then = start.next;

        for (int i = 0; i < n - m; i++) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }

        return dummy.next;
    }

    public ListNode reverseBetween2(ListNode head, int m, int n) {
        if (head == null || m == n) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
        }

        ListNode cur = prev.next;
        ListNode tail = cur;

        prev.next = null;

        for (int i = 0; i <= n - m; i++) {
            ListNode curNext = cur.next;
            cur.next = prev.next;
            prev.next = cur;
            cur = curNext;
        }
        tail.next = cur;

        return dummy.next;
    }
}
